package seqlist.单链表;

/**
 * 基于int的单链表 - 火车
 * 真正被用户使用的是火车类-单链表对象
 */
public class Single_linked_list {

    private Node head;//链表的头节点---火车头
    private int size;//记录有效节点的个数

    /**
     *  向当前的链表中添加一个新的节点，默认在链表的头部添加
     * @param val
     */
    //头插--平常写法
             /*
    public void addFirst(int val){

        Node node = new Node();//创建一个新节点
        node.val = val;

        if(head == null){
            //此时链表为空,第一个节点即为头节点
            head = node;
        }else{
            //此时链表不为空
            node.next = head;//新节点保存现在的头节点地址
            head = node;//头节点保存新的节点地址
        }
        size++;
    }
             */
    //头插--精简写法
    public void addFirst(int val){
        //头插时保存的地址都是当前头节点地址
        Node node = new Node(val, head);
        //如果不存在节点 head == null，那么这样赋值也合理

        head = node;//因为无论是否存在节点，head都会等于新节点地址
        size++;
    }

    /**
     *在任意索引index处插入节点
     */
    public void add(int index, int val){
        //对索引的合法性进行判断
        if(index < 0 || index > size){
            //在插入里面 index可以取到 size，相当于尾插
            System.out.println("插入索引值错误！");
            return;
        }
        //想要插入一个节点，就要找到待插入节点的前驱。
        //所有节点中只有头节点不具备前驱
        if(index == 0){
            addFirst(val);//头插
        }else{
            //开始找头节点，次数是 index - 1次
            Node prve = head;
            for (int i = 0; i < index - 1; i++) {
                 prve = prve.next;
            }//循环出来后说明已经是待插入节点的前驱了
            Node node = new Node(val, prve.next);//新节点连接前驱的下一个地址
            prve.next = node;
            size ++;
        }
    }
    //尾插
    public void addLast(int val){
        add(size, val);
    }

    /**
     * 查询第一个值为 val的索引为多少
     * 不存在则返回 -1
     */
     public int getByValue(int val){

         Node x = head;
         for (int i = 0; i < size; i++) {
             if(x.val == val){
                 return i;
             }
             x = x.next;
         }
         //循环里面没找到就代表不存在
         return -1;//用 -1 表示
     }

    /**
     * 查询索引为index处的节点值为多少
     */
     public int get(int index){
         if(rangeCheck(index)){
             Node prve = head;
             //想走到index处的节点需要走 index 次
             for (int i = 0; i < index; i++) {
                 prve = prve.next;
             }
             return prve.val;
         }
         //走到这说明索引值不合理
         System.out.println("查询索引不合理");
         return -1;
     }
    /**
     * 查询是否包含指定值的节点
     */
     public boolean contains(int val){
         if(getByValue(val) == -1){
             return false;
         }
         return true;
     }


    /**
     * 判断给的index索引是否合理
     */
      private boolean rangeCheck(int index){
          if(index < 0 || index >= size){
              return false;
          }
          return true;
      }

    /**
     * 给你一个index索引，返回给节点的地址，不存在则为null
     */
     private Node node(int index){
         if(rangeCheck(index)){
             Node rep = head;
             for (int i = 0; i < index; i++) {
                 rep = rep.next;
             }
             return rep;
         }
         System.out.println("索引值不合理");
         return null;
     }

    /**
     * 修改索引为index位置的结点值为 newVal，返回修改前的节点值
     */
      public int set(int index, int newVal){
          Node cur = node(index);
          if(cur != null){
              int rep = cur.val;
              cur.val = newVal;
              return rep;
          }
          System.out.println("修改索引值不合理");
          return -1;
      }

    /**
     * 删除 index 处的节点,并返回删除的节点值
     */
      public int remove(int index){

          //需要考虑一种特殊情况，当size == 0没有节点时，不能删除了
          if(size == 0){
              return -1;
          }

          if(rangeCheck(index)){
              //删除一个节点其实也是在找前驱节点的过程
              //但头节点不存在前驱，所以需要特殊考虑
              if(index == 0){
                  //头删
                  Node cur = head;//保存原来的头节点
                  head = head.next;//头节点直接向后移一位
                  //真正删除一个节点最好的方式就是断开所有的连接线
                  //这样才会被JVMN视为系统垃圾被删除
                  cur.next = null;//置空
                  size--;//有效节点个数
                  return cur.val;//返回待删除节点的值
              }else{
                  //索引合法，不是头节点，那就找前驱
                  //我们之前写了 node方法找个index位置处的节点地址
                  //那么 index - 1就是前驱地址了
                  Node cur = node(index - 1);//前驱地址
                  Node node = cur.next;//待删除节点地址
                  cur.next = node.next;//前驱连接下一个的下一个节点地址
                  node.next = null;//断开连接，置空
                  size--;//有效节点个数
                  return node.val;
              }

          }
          System.out.println("删除节点的索引错误");
          return -1;
      }


     //头删
     public int removeFrist(){
          return remove(0);
     }
    //尾删
    public int removeLast(){
        return remove(size - 1);
    }


    /**
     * 删除第一个值为val的节点，并返回它索引
     */
     public int removeValue(int val){
         Node prve = head;
         for (int i = 0; i < size; i++) {
              if(prve.val == val){
                  remove(i);//删除
                  return i;//返回索引值
              }
              prve = prve.next;
         }
         return -1;//说明不存在val值
     }


    /**
     *  删除全部值为 val 的节点
     */
     public void removeAllValue(int val){

        //删除跟插入很像，都是找前驱的过程，但必须先处理头节点
         while(head != null && head.val == val){
              Node x =head;//保存待删除的头节点
              head = head.next;//头节点后移
              x.next = null;
              size--;
         }

         //判断是否被删完了
         if(head == null){
             return;
         }

         //到这里说明头节点不是待删除节点了，而且还要节点需要我们判断
         Node node = head;
         while( node.next != null){
             if(node.next.val == val){
                 Node cur = node.next;//保存待删除的节点
                 node.next = node.next.next;
                 cur.next = null;//断开
                 size--;
             }else{
                 // 只有当node.next.val != val才能移动node指针！
                 node = node.next;
             }
         }
     }


    /**
     * 完善一下toString方法
     */
    public String toString(){
        String rep = "";
        //一定要创建一个变量来变量，如果直接用
        //head来变量的话就丢失原来的地址，找不到头节点了
        for (Node x = head; x != null ; x = x.next) {
            //走到尾节点为null地址算结束
            rep += x.val;
            rep += " -> ";
        }
        rep += "NULL";//用来表示链表走到空了
        return rep;
    }

}

/**
 * 单链表的具体的每个节点 - 车厢类
 */
class Node{

    int val;//每个节点保存的值
    Node next;//当前节点的下一个节点地址

    //无参构造
    public Node() { }

    //有参构造一
    public Node(int val){
        this.val = val;
    }
    //有参构造二
    public Node(int val, Node next){
        this.val = val;
        this.next = next;
    }

}
